LeetCode 75 Level 1 - Day 3 Linked List

206. Reverse Linked List

• 題目連結
• 難易度：Easy

題目敘述

Given the head of a singly linked list, reverse the list, and return the reversed list.

預設函數

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

struct ListNode* reverseList(struct ListNode* head){

}

題目輸入限制

• The number of nodes in the list is the range [0, 5000].
• -5000 <= Node.val <= 5000

解題過程及程式碼

本題是linked list的第二題，給1個linked list，然後回傳1個linked list，它的順序和輸入linked list的順序是反過來的，如下圖Fig. 1所示，Input: head = [1,3,5,7,9]，Output: [9,7,5,3,1]。

接續昨天我們繼續來複習linked list常用的操作：

• 向list的最後新增節點

  node *new_node;
  new_node = getnode();  // (node *) malloc(sizeof(node));
  new_node -> next = NULL;
  ptr->next = new_node  // 指向新節點
  

• 向list的最前面新增節點

  head = new_node;
  new_node->next = ptr;
  

本題想法是將輸入的第一個節點 (node)當作輸出list的head，之後的每一個節點都加在該list最前面，最後記得檢查輸入是否為空節點。

• 程式碼上傳：

  struct ListNode* reverseList(struct ListNode* head){
      struct ListNode *output_head, *output_head_temp, *ptr, *ptr_next_temp;
      output_head = (struct ListNode*)malloc(sizeof(struct ListNode));
      output_head->next = NULL;
  
      if (head == NULL) {
          return NULL;
      }
  
      ptr = head;    
      output_head->val = ptr->val;
      ptr = ptr->next;
  
      while (ptr != NULL) {
          output_head_temp = output_head;
          ptr_next_temp = ptr->next;
  
          output_head = ptr;
          output_head->next = output_head_temp;        
          ptr = ptr_next_temp;
      }
      return output_head;
  }
  

第六天就到這邊，謝謝大家!